/* 先序非递归遍历二叉树 */
#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 先序非递归遍历二叉树 -- 方法一
void Nonpre(BTNode *bt) 
{
  // 创建栈
  BTNode *Stack[maxsize];
  int top = -1;
  
  // 如果二叉树不为空
  if (bt != NULL)
  {
    // 根结点进栈
    Stack[++top] = bt;
    
    // 如果栈不为空
    while (top != -1)
    {
      // 出栈，并打印
      bt = Stack[top--];
      cout << bt->data;
      
      // 右孩子入栈
      if (bt->rchild != NULL)
        Stack[++top] = bt->rchild;
      
      // 左孩子入栈
      if (bt->lchild != NULL)
        Stack[++top] = bt->lchild;
    }
  }
}

// 先序非递归遍历二叉树 -- 方法二
void Nonpre2(BTNode *bt) 
{
  // 创建栈
  BTNode *Stack[maxsize];
  int top = -1;
  
  // 结点不为空 或者 栈不为空
  while (bt || top != -1)
  {
    // 如果二叉树不为空
    if (bt != NULL)
    {
      // 进栈并打印
      cout << bt->data;
      Stack[++top] = bt;
      
      // 到左孩子结点
      bt = bt->lchild;
    }
    
    else
    {
      // 出栈
      bt = Stack[top--];
      
      // 到右孩子结点
      bt = bt->rchild;
    }
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 先序非递归遍历二叉树
  Nonpre2(T);
  return 0;
}
